\documentclass{article}
\usepackage{mathtools} 
\usepackage{fontspec}
\usepackage[UTF8]{ctex}
\usepackage{amsthm}
\usepackage{mdframed}
\usepackage{xcolor}
\usepackage{amssymb}
\usepackage{amsmath}

\newmdtheoremenv[
  backgroundcolor=gray!10,
  linewidth=0pt,
  innerleftmargin=10pt,
  innerrightmargin=10pt,
  innertopmargin=10pt,
  innerbottommargin=10pt
]{zgraytheorem}{}
% 定义说明环境样式
\newtheoremstyle{mystyle}% 说明环境样式的名称
  {1em}% 上方间距
  {1em}% 下方间距
  {\normalfont}% 说明内容的字体样式
  {}% 缩进量
  {\bfseries}% 说明标记的字体样式
  {.}% 说明标记和说明内容之间的标点
  {1em}% 说明标记后的水平空间
  {}% 说明标记后的垂直空间
% 使用新定义的样式创建说明环境
\theoremstyle{mystyle}
\newtheorem*{zremark}{说明}


\begin{document}
\title{8.1 习题}
\maketitle

\section*{8.1.1}

\begin{itemize}
  \item $\Leftarrow$即：$Y \subsetneq X$，$X,Y$有相同的基数，此时$X$是无限集。

        反证法，假设$X$一定是有限集。因为$Y$是$X$的真子集，由命题3.6.14可知，
        $\#(X) < \#(Y)$，与$X,Y$有相同的基数相矛盾。
  \item $\Rightarrow$假设$X$是一个无限序列，然后构造一个双射
        $f: X \rightarrow Y$，$Y \subsetneq X$。

        先以递归的方式定义一个无限序列$(A_n)_{n=0}^\infty$。
        因为$X$是非空集合，所以存在$a_0 \in X$。我们定义$A_0 := \{x_0\}$。
        那么，又因为$X$是无限集，所以$X \setminus A_0$也是无限集，于是可以用相同方式定义
        $A_1 := A_0 \cup \{a_1\}$。
        假设$A_n$已经以递归的方式定义出来，现在证明$A_{n+1}$的存在性，这样才能说明构造方式的正确性。
        因为对所有的$A_i, i \leq n$都是有限集，所以$A \setminus \bigcup _{i=0}^n A_i$是无限集，
        所以，我们可以从中找出一个元素$a_{n+1}$，令$A_{n+1} := A_n \cup \{a_{n+1}\}$。
        至此，$A_n, n \in \mathbb{N}$的存在性得到证明（归纳原理），又因为选择公理可知，
        $A := \bigcup _{n \in \mathbb{N}} A_n$是存在且非空的。

        现在定义$Y := X \setminus \{ a_0 \}$，然后定义函数$f: X \rightarrow Y$如下：
        \begin{equation*}
          \begin{cases*}
            \begin{aligned}
               & f(x) = x       & \text{if } x \in X \setminus A \\
               & f(x) = a_{n+1} & \text{if } x \in A, x = a_n
            \end{aligned}
          \end{cases*}
        \end{equation*}
        显然，$f$是双射函数，命题得证。




\end{itemize}

\section*{8.1.2}
（1）如果$X$是有限集合，则由自然数的三歧性，经过有限次比较，就可以得到最小元素存在。

（2）$X$是无限集

$\bigstar$ \textbf{最大下界方式}

因为$X$是自然数集的非空子集，那么对任意$x \in X, x \geq 0$，即：集合$X$有下界，
由定理5.5.9可知集合$X$有最大下界，不妨设为$m$。

现在需要证明$m \in X$。

反证法，假设$m \not \in X$。

由假设可知任意$x \in X, x > m$。
因为$m \geq \lfloor m \rfloor$（注4.4.2中$\lfloor m \rfloor$表示$m$的整数部分），
于是$x > \lfloor m \rfloor$，
由命题2.2.12（e）可知$x \geq \lfloor m \rfloor + 1$，
那么，$\lfloor m \rfloor + 1$也是$X$的下界，
而$\lfloor m \rfloor + 1 > m$，这与$m$是$X$的最大下界矛盾。

$\bigstar$ \textbf{无穷递降原理方式}

假设$X$没有最小元素，即：任意$x \in X$，存在$x^\prime \in X, x^\prime < x$。

现在构造出序列$(a_n)_{n=0}^\infty$。因为$X$是非空的，所以存在$x_0 \in X$，定义$a(0) := x_0$，
递归定义$a(n+1) := x_{n+1} (x_{n+1} < a(n))$，由之前的说明可知$x_{n+1}$是存在的。

显然这个序列与无穷递降原理矛盾。

$\bigstar \textbf{自然数替换成整数}$

“最大下界方式”的证明方式，显然对整数也是合适，所以替换成整数，良序定理对整数是成立。

$\bigstar \textbf{自然数替换成有理数}$

\section*{8.1.3}

$\bigstar \textbf{因为$X$是无限集，所以集合$\{x \in X: \text{对所有的$m < n$均有$x \neq a_m$}\}$也是无限集}$

设$A =: \{x \in X: \text{对所有的$m < n$均有$x \neq a_m$}\}$，
设$B =: \{a_m: i < n\}$。

反证法，假设$A$不是无限集。又$B$是有限集，
那么，由命题3.6.14（b）可知，$X$是有限集，这与$X$是无限集矛盾。

$\bigstar (a_n)_{n=0}^\infty \textbf{是一个递增序列} $

反证法，假设$(a_n)_{n=0}^\infty$不是递增序列。

由假设可知，存在$k, a_k \geq a_{k+1}$。

由序列的定义可知$a_{k+1} := min\{x \in X: \text{对所有的$m < k+1$均有$x \neq a_m$}\}$，
因为$k < k+1$，所以$a_k = a_{k+1}$是不存在的。

另外，$a_k > a_{k+1}$也是不可能的，因为$a_k$比$a_{k+1}$先定义，
由$min$函数的定义可知，先取出的$a_k$肯定小于$a_{k+1}$。

于是，与假设相悖。

$\bigstar \textbf{对所有的}n \neq m \textbf{均有} a_n \neq a_m$

由$(a_n)_{n=0}^\infty$严格递增保证。

$\bigstar a_n \in X$。

由$a_n$的定义方式保证。

$\bigstar \textbf{表明}$

由$n$的任意性保证的，因为如果存在$m$使得$a_m = x$，则前提不成立了。


$\bigstar a_n \geq n$。

对$n$进行归纳。

归纳基始，$n=0$，由于$a_n$是自然数，所以$a_n \geq 0$。

归纳假设，$n=k$，$a_k \geq k$。

当$n=k+1$时，因为$a_n$是一个递增序列，所以$a_{k+1} > a_k$，即$a_{k+1} > k$，
由命题2.2.12（e）可知$a_{k+1} \geq k+1$。

归纳完成。

$\bigstar \textbf{必然有?}$

良序定理保证最小值的唯一性。

\section*{8.1.4}

有一点需要注意，值域$f(N)$可能不是$Y$，但在以下的证明中，可以把$Y$视为值域$f(N)$。

$\bigstar$ $Y$是有限集时，命题显然成立。

$\bigstar$ $Y$是无限集时。

通过提示可知，$f$是从$A$到$f(A)$的双射是显然的。

下面我们需要证明的是$f(A)$与$Y$是相等的集合，那个$Y$就是可数的了。

由$f(A)$的定义方式可知，$f(A)$中的元素，一定属于$Y$。

对任意$y \in Y$，存在自然数集合$B$，任意$b \in B$使得$f(b) = y$，
取$B$中的最小值$n$，现在需要证明$n \in A$。

对$n$进行强归纳。

归纳基始，$n = 0$，因为不存在自然数$m < 0$，所以$0 \in A$。

归纳假设，$n \leq k$时，$n \in A$。

$n = k+1$时，反证法，假设$k + 1 \neq A$，那么，存在$m < k+1$使得$f(m) = f(k+1)$，
此时，$m \in B$，且$m < k+1$，与$n$是$B$中的最小值矛盾，于是$k + 1 \in A$。

归纳完成。

所以，$n \in A$，即：$y \in f(A)$。

\section*{8.1.5}

因为$X$是可数集，那么存在一个双射$g: \mathbb{N} \rightarrow X$。

所以，由定义3.3.10（复合）可以构造出函数$f \circ g: \mathbb{N} \rightarrow Y$，
由命题8.1.8可知$f \circ g(\mathbb{N})$是至多可数的。

又因为$f(X)$与$f \circ g(\mathbb{N})$是相等的集合（证明略），于是$f(X)$是至多可数的。

\section*{8.1.6}

$\bigstar \Rightarrow$

$A$是至多可数的，如果$A$是有限集，则结论是显然的。

如果$A$是可数集，那么存在一个双射$g: A \rightarrow \mathbb{N}$，
令$f = g$。

$\bigstar \Leftarrow$

（1）如果$f(A)$是有限集，则结论是显然的。

（2）如果$f(A)$是无限集，则需要进一步证明。

因为$f$是单射，那么存在$f(A) \subseteq \mathbb{N}$。

因为$A$不能是空集，存在元素$a_0 \in A$。

现在定义函数$h: \mathbb{N} \rightarrow A$为
\begin{align*}
  h(n) & := f^{-1}(n) & \{n \in \mathbb{N}: n \in f(A) \}      \\
  h(n) & := a_0       & \{n \in \mathbb{N}: n \not \in f(A) \} \\
\end{align*}

由命题8.1.8可知，$A$是至多可数的的。
\section*{8.1.7}

$h(\mathbb{N}) = X \cup Y$是显然的（证明略），由命题8.1.8可知$X \cup Y$是至多可数的。

假设$X \cup Y$是有限集，那么由命题3.6.14（c）可知$X$是有限的，这与题设矛盾。

\section*{8.1.8}

由推论8.1.9可知，只要找到一个函数$f: \mathbb{N} \times \mathbb{N} \rightarrow X \times Y$，
那么，$f(\mathbb{N} \times \mathbb{N})$是至多可数的。
然后只需说明$X \times Y = f(\mathbb{N} \times \mathbb{N})$。那么，$X \times Y$也是至多可数的。

因为$X$是可数集，所以存在一个双射函数$g: \mathbb{N} \rightarrow X$；

同理，存在一个双射函数$h: \mathbb{N} \rightarrow Y$；

现在定义函数$f: \mathbb{N} \times \mathbb{N} \rightarrow X \times Y$为
\begin{align*}
  f(n,m) := (g(n), h(m))
\end{align*}

接下来，要证明$X \times Y = f(\mathbb{N} \times \mathbb{N})$。

反证法，假设$X \times Y \neq f(\mathbb{N} \times \mathbb{N})$，
那么，至少存在一个元素$(x,y) \in X \times Y$且$(x,y) \not \in f(\mathbb{N} \times \mathbb{N})$。
因为$x \in X, y\in Y$，所以存在$(n,m)$使得$x = g(n), y=h(m)$，
又因为$(n,m) \in \mathbb{N} \times \mathbb{N}$，
而$(g(n),h(m)) \in f(\mathbb{N} \times \mathbb{N})$，即：
$(x,y) \in f(\mathbb{N} \times \mathbb{N})$，与假设矛盾。


\section*{8.1.9}

这道题，直觉上是显然的，但着手证明时，又十分困难，主要有些问题难以处理：

\begin{itemize}
  \item $I，A_{\alpha}$都是至多可数的，这表明，既可以是有限集，也可以是可数集。
  \item 直觉上，我们有一个至多可数的集合序列$A_{\alpha}$，而$A_{\alpha}$本身也是至多可数的，
  好像$\bigcup \limits_{\alpha \in I} A_{\alpha}$中的元素，可以用两个下标表示，然后就会很自然的
  想到$\mathbb{N} \times \mathbb{N}$与$\bigcup \limits_{\alpha \in I} A_{\alpha}$存在映射。
  但题设中没有说明$A_{\alpha}$之间是不相交的，这样就不能假设该映射是双射的
  （因为同一个$x$可以同时属于多个$A_{\alpha}$）。
\end{itemize}

如何克服这些困难，要说明集合$A$是至多可数的，无需找到一个双射函数，比如单射函数$f: A \rightarrow C$，
其中$C$是之多可数的，那么$A$也是至多可数的（因为$A$与$f(A)$之间是双射，于是$A$与$f(A)$之间的基数相同，
$f(A)$是$C$的子集，推论8.1.7可知$f(A)$是至多可数的，所以$A$也是之多可数的。）。
特别的，如果$A$与$\mathbb{N}$间有单射函数，则$A$是至多可数的。

以单射替换双射的方式，进行我们的证明。

\begin{itemize}
  \item 因为$I$是至多可数的，那么，存在一个双射$g: N \rightarrow I$，这里$N$是$\mathbb{N}$的子集。
  \item 因为$A_{g(m)}$也是至多可数的，那么，存在一个单射$f_m : A_{g(m)} \rightarrow \mathbb{N}$。
  对所有$m \in N$, 设$F_m$是所有$A_{g(m)} \rightarrow \mathbb{N}$的函数集合。由于$F_m$是非空的，
  由选择定理可知，我们可以在每个集合中选一个单射函数，得到一个至多可数集合$\{f_m\}_{m \in N}$。
  \item 现在可以考虑$x \in \bigcup \limits_{\alpha \in I} A_{\alpha} = \bigcup \limits_{m \in N} A_{g(m)}$，
  $x$属于多个$A_{g(m)}$这个问题了。集合$\{m \in N : x \in A_{g(m)}\}$，因为集合是$\mathbb{N}$的子集，
  由良序原理（命题8.1.4）可知，该集合存在一个最小值$n$。
  \item 现在定义一个函数$h: \bigcup \limits_{m \in N} A_{g(m)} \rightarrow \mathbb{N} \times \mathbb{N}$，
  对所有$x \in \bigcup \limits_{m \in N} A_{g(m)}$，定义$h(x) = (n, f_n(x))$，其中$n$是之前定义的最小值。
  $h$是单射的，因为对任意$x$，$n$是唯一的，并且$f_n$是单射函数。
  于是$\bigcup \limits_{m \in N} A_{g(m)}$是至多可数的。
\end{itemize}

\section*{8.1.10}
没找到！

\end{document}